Random Walk, Brownian Motion and Heat Equation

---

One dimensional random walk

Let $X_n$ denotes the step of the walker at time n, $S_n$ denotes the position of the walker at time n. We have the following relationship:

$$S_n = x_0 + X_1 + X_2 + \cdots + X_n$$

where $x_0$ is the initial starting point of the walker.

Here are some properties of each step $X_n$:

• $\mathbb{P} \lbrace X_j=1\rbrace = \mathbb{P} \lbrace X_j=-1\rbrace = \frac{1}{2}$
• $\mathbb{E} X = \sum_z z \mathbb{P} \lbrace X=z\rbrace = 0$
• $\text{Var}(S_n) = \mathbb{E} S_n^2 = n$

Boundary value problems

Let $T = \min \lbrace n:S_n \in \{ 0, N \} \rbrace$, then we observe that $\mathbb{P}\lbrace T < \infty\rbrace=1$. It indicates that the random walk must come back in finite time. Hence, we can define the following function $F$.

Definition Function $F : \lbrace 0,\ldots,N\rbrace \rightarrow [0,1]$

$$F(x) =\mathbb{P}\lbrace S_T = N\mid S_0 = x\rbrace$$

then we can get boundary conditions $F(0) = 0, F(N) = 1$ and recurrence relation $F(x) = \frac{1}{2}\, F(x+1) + \frac{1}{2}\, F(x-1),\quad x = 1,\ldots,N-1$.

By observation, the function $F(x) = x/N$ satisfies the boundary conditions. Actually, we can prove that it is the only such function.

Theorem Suppose $a$, $b$ are real numbers and $N$ is a positive integer. Then the only function $F : \lbrace 0,\ldots,N\rbrace \rightarrow\mathbb{R}$ satisfying the equation above with $F(0) = a \text{and} F(N) = b$ is the linear function $F(x) = a + \frac{x(b - a)}{N}$.

Higher dimensional case

In higher dimensional space, we can do pretty much the same. Replace $\lbrace1,\ldots,N\rbrace$ with finite connected subset $A \subset \mathbb{Z}^d$ and define $\partial A = \lbrace z \in \mathbb{Z}^d\, \backslash \, A : \text{dist} (z,A) = 1\rbrace$ to be all the boundary points. Plus, it is helpful to know the following definition.

Definition $\mathcal{Q}, \mathcal{L}$ are linear operatos on function $F$, s.t.

$$\begin{align*} \mathcal{Q}F(x) = \frac{1}{2 d} \sum_{y \in \mathbb{Z}^d,\ |x-y| = 1} F(y), \qquad \qquad \qquad \\ \mathcal{L}F(x) = (\mathcal{Q} - \mathbb{I})F(x) = \frac{1}{2d} \sum_{y \in \mathbb{Z}^d,\ |x-y| = 1} [F(y) - F(x)] \end{align*}$$

Dirichlet problem for discrete harmonic functions

Now we define a harmonic function as the following.

Definition Given a set $A \subset \mathbb{Z}^d$ and a function $F : \partial A \rightarrow \mathbb{R}$ in an extension of $F$ to $\bar{A}$, $F$ is harmonic in $A$ if

$$\mathcal{L}F(x) = \mathbb{E}[F(S_1) - F(S_0)\mid S_0 = x] = 0\ \text{for all}\ x \in A$$

Similar to one dimensional case, we have

• $T_A = \min \lbrace n \geq 0 : S_n \notin A \rbrace$
• $\mathbb{P} \lbrace T_A < \infty\rbrace = 1$

An important theorem therefore follows

Theorem If $A \subset \mathbb{Z}^d$ is finite, then for every $F : \partial A \rightarrow \mathbb{R}$, there is an unique extension of $F$ to $\bar{A}$ that satisfies $\mathcal{L}F(x) = 0$.

$$\begin{align*} F(x) = \mathbb{E}[F(S_{T_A})\mid S_0 = x] = \sum_{y \in \partial A} \mathbb{P}\lbrace S_{T_A} = y\mid S_0 = x\rbrace F(y) \end{align*}$$

Heat equation

Set the temperature at the boundary to be zero at all times and as an initial condition set the temperature at $x \in A$ to be $f_0(x)$. For $x \in A$,

$$p_{n+1}(x) = \frac{1}{2d} \sum_{|y-x|=1} p_n(y)$$

Definition Let $\partial_n p_n(x) = p_{n+1}(x) - p_n (x)$, we have heat equation

$$\begin{align*} \partial_n p_n(x) &= \mathcal{L} p_n(x), \quad x \in A\\ &\\ p_0(x) &= f_0(x), \quad x \in A\\ p_n(x) &= 0, \quad x \in \partial A. \end{align*}$$

Brownian motion

Basic properties of Brownian motion:

• $W_t$ be the position of the Brownian motion at time $t$.
• $\Delta t = \delta = 1/N$
• For large $N$, $$\begin{align*} W_{k\delta} &\approxeq \Delta x\, S_k\\ \mathbb{E}[(W_1)^2] = \mathbb{E}[(\Delta x S_N)^2] &= (\Delta x)^2 \mathbb{E} [S_N^2] = (\Delta x)^2 N = 1 \end{align*}$$
• $\Delta x = 1/ \sqrt{N} = \sqrt{\delta}$
• $t = j\delta = j/N \Rightarrow W_t = W_{j/N} = \frac{S_j}{\sqrt{N}}$
• $W_t \approx \frac{S_j}{\sqrt{N}} = \frac{S_j}{\sqrt{j}}\sqrt{\frac{j}{N}} = \frac{S_j}{\sqrt{j}} \sqrt{t}$
• $W_t$ has a normal distribution with $\mathbb{E}[W_j] = 0$ and $\text{Var}[W_j] = t$.
• $W_t \approx \frac{S_j}{\sqrt{N}} = \frac{S_j}{\sqrt{j}}\sqrt{\frac{j}{N}} = \frac{S_j}{\sqrt{j}} \sqrt{t}$
• $W_t$ has a normal distribution with $\mathbb{E}[W_j] = 0$ and $\text{Var}[W_j] = t$.

Similarly, we can find if the function is harmonic by the following theorem.

Theorem A function $f$ in a domain $U$ is harmonic if and only if $f$ is $C^2$ with $\Delta f(x) = 0$ for all $x \in U$.

Heat Equations

Definition With $f(x)$ being the initial temperature at $x$, $u(t,x), t \geq 0, x \in \mathbb{R}^d$ denotes the temperature at $x$ at time $t$.

$$\begin{align*} u&(t,x) = \mathbb{E}[f(W_t)\ |\ W_0 = x]\\ \\ \partial_t &u(t,x) = \frac{1}{2} \mathcal{L}\, u(t,x)\\ \partial_t &u(t,x) = \frac{1}{2} \Delta_x u(t,x) \end{align*}$$

Brownian Meander

Brownian motion:

$$\psi_t (x) = \frac{1}{\sqrt{2\pi t}} \mathrm{e}^{-\frac{x^2}{2t}}$$

Brownian meander:
$\mathcal{M}\,(t)$ be a Brownian meander, $\mathfrak{M}(t) = \max_{0<s<t} \mathcal{M}\,(s)$

$$\begin{align*} \mathbb{P}(\mathcal{M}(1)<x&, \mathfrak{M}(1)<y) = \sum_{k = -\infty}^\infty [\mathrm{e}^{-\frac{(2ky)^2}{2\sigma^2}}-\mathrm{e}^{-\frac{(2ky+x)^2}{2\sigma^2}}]\\ \phi(l,s) &= \lim_{dx \rightarrow 0} \frac{1}{dx} \mathbb{P}\lbrace \mathcal{M}(1) \in [l,l+dx], \mathfrak{M}(1)<s\rbrace\\ &= \sum_{k = -\infty}^\infty \frac{2ks+l}{\sigma^2}\mathrm{e}^{-\frac{(2ks+l)^2}{2\sigma^2}} \end{align*}$$

One Dimensional Injection Process

Constantly injecting from the right endpoint of line segment $[0,1]$, then the density of particle at $x$ from time $-b$ to $-a$ is\cite{equ},

$$\begin{align*} d(x,a,b) = \int_{a}^{b} \sum_{k=-\infty}^\infty \frac{2k+x}{\sigma^2} \mathrm{e}^{-\frac{(2k+x)^2 t^2}{2\sigma^2}} dt \end{align*}$$

The equilibrium density function at $x$ is,

$$\begin{align*} d(x) &= \lim_{\substack{a = 0\\ b \rightarrow \infty}} \int_{a}^{b} \sum_{k=-\infty}^\infty \frac{2k+x}{\sigma^2} \mathrm{e}^{-\frac{(2k+x)^2 t^2}{2\sigma^2}} dt\\ &= \int_{0}^{\infty} \sum_{k=-\infty}^\infty \frac{2k+x}{\sigma^2} \mathrm{e}^{-\frac{(2k+x)^2 t^2}{2\sigma^2}} dt \end{align*}$$ $$\begin{align*} d(x) =& \lim_{\delta \rightarrow 0} \int_{\sqrt{\delta}}^{\frac{1}{\sqrt{\delta}}} \sum_{k=-\infty}^\infty \frac{2k+x}{\sigma^2} \mathrm{e}^{-\frac{(2k+x)^2 t^2}{2\sigma^2}} dt \qquad \qquad \qquad \qquad \qquad \\ =& \lim_{\delta \rightarrow 0} \int_{\sqrt{\delta}}^{\frac{1}{\sqrt{\delta}}} \frac{x}{\sigma^2} \mathrm{e}^{- \frac{x^2t^2}{2\sigma^2}} dt + \lim_{\delta \rightarrow 0} \int_{\sqrt{\delta}}^{\frac{1}{\sqrt{\delta}}} \sum_{k=1}^\infty \frac{2k+x}{\sigma^2} \mathrm{e}^{-\frac{(2k+x)^2 t^2}{2\sigma^2}} dt \\ &+ \lim_{\delta \rightarrow 0} \int_{\sqrt{\delta}}^{\frac{1}{\sqrt{\delta}}} \sum_{k=-1}^{-\infty} \frac{2k+x}{\sigma^2} \mathrm{e}^{-\frac{(2k+x)^2 t^2}{2\sigma^2}} dt\\ =& \ \cdots\\ =& \frac{\sqrt{2\pi}}{\sigma} + \frac{2\sqrt{2\pi}}{\sigma} \left(-\frac{x}{2}\right) = \frac{\sqrt{2\pi}(1-x)}{\sigma} \end{align*}$$

Injection to Planar Domains

• Set $A = \lbrace(a,b)\, |\, a \in [0,1], b \in [0,1]\rbrace \subset \mathbb{R}^2$ being the domain.
• For $\forall \text{point} x \in \lbrace (a,b) | b = 0\rbrace$, $x$ can be an injection point, with intensity function $f(x)$.
• For $\forall \text{point} P = (l_1,l_2) \in \lbrace(a,b) | 0\leq a \leq 1, 0 < b \leq 1\rbrace$, $P$ has initial density function $d_0(P) = 0$.
• The motion of the particles can be separated into two independent parts:
  • A Brownian motion $\mathcal{B}(t)$ on $x$ axis.
  • A Brownian meander $\mathcal{M}(t)$ on $y$ axis.

Since probability density function $\phi$ of Brownian meander $\mathcal{M}(t)$ reaching $l$ in time 1 without touching 1 is,

$$\phi (1,l) = \sum_{k=-\infty}^\infty \frac{2k+l}{\sigma^2} \mathrm{e}^{-\frac{(2k + l)^2}{2\sigma^2}}$$

We can have probability density $p_1(t,l_2)$ of injected particle with $y$ component at $l_2$ in time $t$,

$$p_1(t,l_2) = \frac{1}{t} \phi \left(\frac{1}{\sqrt{t}}, \frac{l_2}{\sqrt{t}}\right) = \sum_{k = -\infty}^\infty \frac{2k_1+l_2}{t\sqrt{t}} \mathrm{e}^{-\frac{(2 k_1+l_2)^2}{2t}}$$ $$\begin{align*} \mathbb{P} \lbrace \mathcal{B}&(t) \in [x_0 + dx, x_0 - dx], \min \mathcal{B}(t) > x_1, \max \mathcal{B}(t) < x_2\rbrace /dx\\ \qquad \qquad &= \sum_{n = -\infty}^\infty \frac{1}{\sigma \sqrt{t}}\, \left[ \, \phi\left( \frac{x_0-2n(x_2-x_1)}{\sigma \sqrt{t}}\right) \right.\\ \qquad \qquad &\ - \left.\phi\left( \frac{x_0-2n(x_2-x_1)-2x_1}{\sigma \sqrt{t}}\right)\right] \end{align*}$$

The probability density $p_2 (t,l_1,x)$ of a Brownian motion $\mathcal{B}(t)$ starting from $x$ reaches point $l_1$ in time $t$:

$$p_2 (t,x,l_1) = \sum_{k = -\infty}^\infty \frac{1}{\sigma \sqrt{t}} \left[ \phi \left( \frac{x - l_1 - 2k}{\sigma \sqrt{t}} \right) -\phi \left( \frac{3x - l_1 - 2k}{\sigma \sqrt{t}} \right) \right]$$

As the Brownian motion and the Brownian meander are independent from each other,

$$\begin{align*} p(t,x,l_1,l_2) =& p_1 (t,l_2)\, p_2(t,x,l_1)\\ =& \left( \sum_{k_1 = -\infty}^\infty \frac{2k_1+l_2}{t\sqrt{t}} \mathrm{e}^{-\frac{(2 k_1+l_2)^2}{2t}} \right) \cdot \\ & \left( \sum_{k_2 = -\infty}^\infty \frac{1}{\sigma \sqrt{t}} \left[ \phi \left( \frac{x - l_1 - 2k_2}{\sigma \sqrt{t}} \right) -\phi \left( \frac{3x - l_1 - 2k_2}{\sigma \sqrt{t}} \right) \right] \right) \end{align*}$$ $$\begin{align*} p(t,x,l_1,l_2) =& \frac{1}{\sqrt{2\pi}} \left( \sum_{k_1 = -\infty}^\infty \frac{2k_1+l_2}{t\sqrt{t}} \mathrm{e}^{-\frac{(2 k_1+l_2)^2}{2t}} \right)\cdot \\ & \left( \sum_{k_2 = -\infty}^\infty \mathrm{e}^{-\frac{f_1(l_1,k_2,x)}{2t}} - \mathrm{e}^{-\frac{f_2(l_1,k_2,x)}{2t}} \right) \end{align*}$$

where

$$\begin{align*} f_1(l_1,k_2,x) = (l_1 - 2k_2)^2 - 2(l_1 -2k_2)x +x^2\\ f_2(l_1,k_2,x) = (l_1 - 2k_2)^2 + 2(l_1 -2k_2)x +x^2 \end{align*}$$

For $\forall y = (l_1,l_2) \in A$, the accumulated density at $y$ in time $t_0$ is,

$$\begin{align*} h(t_0,l_1,l_2) =& \int_0^{t_0} \int_0^1 p(t,x,l_1,l_2)\,dxdt\\ =& \int_0^{t_0} \frac{1}{\sqrt{2\pi}} \sum_{k_1 = -\infty}^\infty \frac{2k_1+l_2}{t\sqrt{t}} \mathrm{e}^{-\frac{(2 k_1+l_2)^2}{2t}}\cdot \\ & \left(\int_0^1 f(x) \sum_{k_2 = -\infty}^\infty \mathrm{e}^{-\frac{f_1(l_1,k_2,x)}{2t}} - \mathrm{e}^{-\frac{f_2(l_1,k_2,x)}{2t}}\,dx \right) dt \end{align*}$$

Verifying Heat Equation

We can see function $h$ as $h(t_0,l_1,l_2) = \int_0^{t_0} \frac{1}{\sqrt{2\pi}} p_1(t,l_2)\, \widetilde{p_2}(t,l_1)\,dt$,

$$\begin{align*} p_1(t,l_2) =& \sum_{k_1=-\infty}^\infty \frac{2k_1+l_2}{t\sqrt{t}} \mathrm{e}^{-\frac{(2 k_1+l_2)^2}{2t}}\\ \widetilde{p_2}(t,l_1) =& \int_0^1 f(x)\, p_2(t,x,l_1)\,dx\\ =& \int_0^1 f(x) \sum_{k_2 = -\infty}^\infty \left( \mathrm{e}^{-\frac{f_1(l_1,k_2,x)}{2t}} - \mathrm{e}^{-\frac{f_2(l_1,k_2,x)}{2t}}\right)\,dx \end{align*}$$ $$\begin{align*} \frac{\partial p_1}{\partial t}(t,l_2) &= \sum_{k_1 = -\infty}^\infty \frac{(2k_1 + l_2)(4{k_1}^2 l_2 + {l_2}^2 -3t)}{2t^{7/2}} \mathrm{e}^{-\frac{(2k_1 + l_2)^2}{2t}}\\ \frac{\partial^2 p_1}{\partial {l_2}^2}(t,l_2) &= \sum_{k_1 = -\infty}^\infty \frac{(2k_1 + l_2)(4{k_1}^2 l_2 + {l_2}^2 -3t)}{t^{7/2}} \mathrm{e}^{-\frac{(2k_1 + l_2)^2}{2t}}\\ \Rightarrow \frac{\partial p_1}{\partial t}(t,&l_2) = \frac{1}{2} \frac{\partial^2 p_1}{\partial {l_2}^2}(t,l_2), \quad p_1(t,l_2) = \int_0^t \frac{1}{2} \frac{\partial^2 p_1}{\partial {l_2}^2}(s,l_2)\,ds \end{align*}$$

Since $\widetilde{p_2} = \int_0^1 f(x) \sum_{k_2 = -\infty}^\infty \left( \mathrm{e}^{-\frac{f_1(l_1,k_2,x)}{2t}} - \mathrm{e}^{-\frac{f_2(l_1,k_2,x)}{2t}}\right) \,dx$

$$\begin{align*} \frac{\partial \widetilde{p_2}}{\partial t}(t,l_1) &= \int_0^1 f(x) \sum_{k_2 = -\infty}^\infty \frac{\partial}{\partial t} \left( \mathrm{e}^{-\frac{f_1(l_1,k_2,x)}{2t}} - \mathrm{e}^{-\frac{f_2(l_1,k_2,x)}{2t}}\right)\,dx\\ \frac{\partial^2 \widetilde{p_2}}{\partial {l_1}^2}(t,l_1) &= \int_0^1 f(x) \sum_{k_2 = -\infty}^\infty \frac{\partial^2}{\partial {l_1}^2} \left( \mathrm{e}^{-\frac{f_1(l_1,k_2,x)}{2t}} - \mathrm{e}^{-\frac{f_2(l_1,k_2,x)}{2t}}\right)\,dx\\ \Rightarrow \frac{\partial \widetilde{p_2}}{\partial t}(t,&l_1) = \frac{1}{2} \frac{\partial^2 \widetilde{p_2}}{\partial {l_1}^2}(t,l_1), \quad \widetilde{p_2}(t,l_1) = \int_0^t \frac{1}{2} \frac{\partial^2 \widetilde{p_2}}{\partial {l_1}^2}(s,l_1)\,ds \end{align*}$$

Theorem If $u(t,l_1,l_2) = \int_0^t \tilde{h}(s,l_1) \tilde{v}(s,l_2)\,ds$, then $u_t = \frac{1}{2} \Delta u$.

$$\begin{align*} \textit{Proof:}\qquad \qquad \because \frac{\partial u}{\partial t} &= \tilde{h}(s,l_1) \tilde{v}(s,l_2).\\ \Rightarrow \frac{\partial^2 u}{\partial t^2} &= \frac{\partial \tilde{h}}{\partial t}(t,l_1) \tilde{v}(t,l_2) + \tilde{h}(t,l_1) \frac{\partial \tilde{v}}{\partial t}(t,l_2)\\ &= \frac{1}{2} \frac{\partial^2 \tilde{h}}{\partial {l_1}^2}(t,l_1) \tilde{v}(t,l_2) + \frac{1}{2} \tilde{h}(t,l_1) \frac{\partial^2 \tilde{v}}{\partial {l_2}^2}(t,l_2)\\ &= \frac{1}{2} \Delta [\tilde{h}(t,l_1) \tilde{v}(t,l_2)]\\ &= \frac{1}{2} \Delta \frac{\partial u}{\partial t} \end{align*}$$

Claim: $h(t_0,l_1,l_2)$ satisfies heat equation.

$$\begin{align*} \frac{\partial p_1}{\partial t}(t,l_2) &= \frac{1}{2} \frac{\partial^2 p_1}{\partial {l_2}^2}(t,l_2)\\ \frac{\partial \widetilde{p_2}}{\partial t}(t,l_1) &= \frac{1}{2} \frac{\partial^2 \widetilde{p_2}}{\partial {l_1}^2}(t,l_1)\\ h(t_0,l_1,l_2) &= \int_0^{t_0} \frac{1}{\sqrt{2\pi}} p_1(t,l_2)\, \widetilde{p_2}(t,l_1)\,dt \end{align*}$$ $$\begin{align*} \Rightarrow \frac{\partial^2}{\partial t^2} h(t_0,l_1,l_2) = \frac{1}{2} \Delta \frac{\partial}{\partial t} h(t_0,l_1,l_2) \end{align*}$$